1. Field of the Invention
The present invention is related to a protection method for a private key and particularly to an anti-attacking method for an RSA private key, a controller and a storage device executing the method and a computer readable recording medium thereof.
2. Description of Related Art
In a cryptosystem, a code key is applied in relevant computations related to cryptography. As to an asymmetrical cryptosystem Rivest-Shamir-Adleman (RSA), a code key thereof is produced in a pair of a public key and a private key. Usage of “a pair of a public key and a private key” defines two applications. One application is using the private key as a signature key to produce a digital signature on digital information and using the public key as a verifying key to verify if a certain value is a correct signature value. The other application is using the public key as an encrypted key to encrypt a plain text as an encrypted text and using the private key as a decrypting key to decrypt the encrypted text back to the plain text.
A person who executes a digital signature has to keep secrecy of his/her signature key, and a receiver of an encrypted text also has to keep the decrypting key as a secret. Therefore, the private key is a secret. Although the private key is a value related to the public key, disclosure of the public key does not divulge secrecy of the corresponding private key.
In an RSA method, the modular arithmetic is used, wherein a modulus in the modular arithmetic is multiplication of two prime numbers. It is rather difficult to derive a private key from a public key using computation for lack of an efficient algorithm to factorize a multiplication of two prime numbers back to the two original prime numbers.
RSA computation usually involves the modular arithmetic. Modular arithmetic can be defined as follows: Suppose x and y are two integers, when (x-y) can be divisible by z, x and y are called as identical remainders of z as the modulus of modular arithmetic, which is expressed as x-y (mod z).
An RSA key may be produced by following steps:
(1) A positive integer e is selected as an encryption exponent, i.e., a public exponent well-known to people skilled in the art.
(2) Two different prime numbers p and q are selected at random, and both (p−1) and (q−1) are primer numbers with e respectively.
(3) A public modulus is set as n=pq.
(4) A private exponent d is selected to render (de−1) as divisible by both (p−1) and (q−1).
A public exponent e and a modulus n of RSA are used to encrypt a plain text integer m. An encrypted integer c is obtained by calculating c∝me(mod n), wherein m is presumed to be smaller than n. A private exponent d and a modulus n are used to decrypt the encrypted integer c back to the plain integer m through calculating m≡cd(mod n).
The private exponent d and the modulus n in RSA may also be applied in generating a digital signature. First, a message summary for digital information M to be signatured, expressed as hash(M), is generated through a collision-resistant hash function. Next, a digital signature of the digital information M may be obtained through hash(M)d(mod n), which is expressed as signature (M).
The public exponent e and the modulus n in RSA may be used to verify whether a certain value is a correct digital signature. Suppose a verifier receives an M∥SGN, M represents a digital information and SGN represents a digital signature attached to M. First, the verifier uses the already selected collision-resistant hash function to calculate hash(M) and uses a public key (e,n) to decrypt SGN through calculating SGNe(mod n). Next, the verifier compares hash(M) with the decrypted result. If the comparison reveals both to be identical to each other, SGN is a correct signature. A general framework for implementing RSA is, for example, an RSA Rule 1:
0.1Input : M, K, N0.2Output : R = MK mod N0.3R = 1, B = M0.4for i = 0 to length (K)−1,0.5 if (Ki == 1) R = RB mod N0.6 B = B2 mod N0.7end for
In the aforementioned Rule 1, a document R bearing a digital signature is outputted through inputting a document M to which a digital signature is added, an RSA private key K and an RSA modulus N. R and B are security information during operation of RSA. Furthermore, K is 1024 or 2048 bits.
Since the said private key K may be applied in an internet transaction or a smart card which requires identity verification, it has become an object hackers are keen to break. Under such a framework, generally, before a digital signature is outputted, a cryptosystem would verify a digital signature with a public key and only output a computation result when the verification is successful. Accordingly, an attacker intending to steal an RSA private key may perform a fault attack on R of the said formula (0.5) or on B of the said formula (0.6) so as to steal the private key. In other words, the attacker may tamper values of R or B during an operation process to guess the RSA private key K. The following is an attacking method exemplified by tampering R. An implementation framework of modulus multiplication in the formula (0.5) is stated as follows:
1.1Input: R, M, N1.2Output: R = RM mod N 1.3                    Suppose:            ⁢                          ⁢      R        =                  ∑                  j          =          0                          m          -          1                    ⁢                          ⁢                                    R            j                    ⁡                      (                          2              t                        )                          j              ,      m    =          ⌈              n        /        t            ⌉        ,      n    =          length      ⁡              (        R        )             1.4A = 01.5for j = m − 1 to 0,1.6A = (A2t + RjM) mod N1.7end for1.8R = A
It can be known from the said formula (1.5) that in modulus multiplication, a security information R is calculated bit by bit and updated accordingly. If the said formula (1.6) executes j=k<m−1, the attacker attacks (modifies) information Rm−1, Rm−2, . . . , Rk+1. Since the attacker modifies information already calculated, such modification does not result in an erroneous final value A. Therefore, when executing the formula (1.8) at last, modulus multiplication can still obtain a correct R. It is known from the formula (0.5) that if Ki=1, a final computation result is identical to the correct value. On the contrary, if Ki=0, modulus multiplication is not performed, and an attack by the attack would render R as different from the correct value thereof. Hence, if a final operation result of Rule 1 is found to be erroneous, the attacker may infer that the RSA private key Ki is 0. If the operation result is correct, the attacker may infer that the RSA private key Ki is 1.
A general anti-attacking mechanism usually detects an attack as described above before a result is outputted by verifying a computation result with a public key to determine whether to output the result. However, such an approach may detect an attack but cannot ward off the attack since no result is outputted during the attack is also advising the attacker that the operation result is erroneous.
Therefore, an anti-attacking method which prevents an attacker from inferring a private key is necessary to solve the said problem.